package primary.primary0;

public class S0647回文子串 {

    class Solution1 {
        /**
         * 89
         * 遍历每个字符，看这个字符延伸出去，奇数回文串和偶数回文串最长是什么长度，加起来就是以当前这个字符为中心的最大长度
         * 叫中心扩展法
         */
        public int countSubstrings(String s) {
            if(s == null || s.length() == 0){
                return 0;
            }
            int totalCount = 0;
            for(int i = 0; i < s.length(); i++){
                totalCount += oddCount(s, i);
                totalCount += evenCount(s, i);
            }
            return totalCount;
        }

        private int oddCount(String s, int loc){
            int startLoc = loc;
            int endLoc = loc;
            int count = 0;
            // mark: 原来for里面是可以用逗号分割多个语句的
            for(; startLoc >= 0 && endLoc < s.length(); startLoc--, endLoc++){
                if(s.charAt(startLoc) == s.charAt(endLoc)){
                    count++;
                }else{
                    break;
                }
            }
            return count;
        }

        private int evenCount(String s, int loc){
            int startLoc = loc;
            int endLoc = loc + 1;
            int count = 0;
            // mark: 原来for里面是可以用逗号分割多个语句的
            for(; startLoc >= 0 && endLoc < s.length(); startLoc--, endLoc++){
                // mark: char直接==就行
                if(s.charAt(startLoc) == s.charAt(endLoc)){
                    count++;
                }else{
                    break;
                }
            }
            return count;
        }

    }

    /**
     * 和solution1一样，中心扩展
     */
    class Solution2 {
        public int countSubstrings(String s) {
            int n = s.length(), ans = 0;
            for (int i = 0; i < 2 * n - 1; ++i) {
                // 这里处理左右的方式答案说是通过观察法得出来的，目测有点麻烦，而且边界值搞不好摸不清，就留意一下，不学
                int l = i / 2, r = i / 2 + i % 2;
                while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                    --l;
                    ++r;
                    ++ans;
                }
            }
            return ans;
        }
    }

    static class Solution3{
        /**
         * 29
         * 动态规划，自己实现一下，就是二维化，f(i, j)表示i->j是否为回文子串，那么必然 f(i + 1， j - 1)是回文子串 且char i = char j
         * mark: 如何跳出多重循环 https://blog.csdn.net/m0_46284149/article/details/127068688
         */
        public static int countSubstrings(String s) {

            if(s == null || s.length() == 0){
                return 0;
            }
            int totalCount = 0;

            // mark: 二维数组初始化不能忘了
            int[][] record = new int[s.length()][s.length()];
            // 这里要注意下遍历顺序，建议画个图，然后看下每个点依赖的是那个点，看下怎么遍历
            for(int i = s.length() - 1; i >= 0; i--){
                for(int j = i; j < s.length(); j++){
                    if(s.charAt(i) != s.charAt(j)){
                        continue ;
                        // 这里本来写的是break，注意break相当于 这个break所在的第一个for，整个都不执行了
                    }
                    if(i == j){
                        record[i][j] = 1;
                        totalCount ++;
                    } else if (j - i == 1) {
                        record[i][j] = 1;
                        totalCount ++;
                    }else{
                        if(record[i + 1][j - 1] == 1){
                            record[i][j] = 1;
                            totalCount ++;
                        }
                    }
                }
            }
            return totalCount;
        }

        public static void main(String[] args) {
            new Solution3().countSubstrings("aba");
        }


    }



}
